home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 July / macformat-026.iso / mac / Shareware City / Developers / berkeleydb1.73 / Berkeley_db / btree / bt_split.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  21.7 KB  |  831 lines  |  [TEXT/MPS ]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_split.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #if defined(macintosh) && (defined(powerc) || defined(__powerc))
  42. #include "OurMalloc.h"
  43. #endif
  44.  
  45. #include <sys/types.h>
  46.  
  47. #define    __DBINTERFACE_PRIVATE
  48. #include <limits.h>
  49. #include <stdio.h>
  50. #include <stdlib.h>
  51. #include <string.h>
  52.  
  53. #include <db.h>
  54. #include "btree.h"
  55.  
  56. static int     bt_broot __P((BTREE *, PAGE *, PAGE *, PAGE *));
  57. static PAGE    *bt_page
  58.             __P((BTREE *, PAGE *, PAGE **, PAGE **, u_int *, size_t));
  59. static int     bt_preserve __P((BTREE *, pgno_t));
  60. static PAGE    *bt_psplit
  61.             __P((BTREE *, PAGE *, PAGE *, PAGE *, u_int *, size_t));
  62. static PAGE    *bt_root
  63.             __P((BTREE *, PAGE *, PAGE **, PAGE **, u_int *, size_t));
  64. static int     bt_rroot __P((BTREE *, PAGE *, PAGE *, PAGE *));
  65. static recno_t     rec_total __P((PAGE *));
  66.  
  67. #ifdef STATISTICS
  68. u_long    bt_rootsplit, bt_split, bt_sortsplit, bt_pfxsaved;
  69. #endif
  70.  
  71. /*
  72.  * __BT_SPLIT -- Split the tree.
  73.  *
  74.  * Parameters:
  75.  *    t:    tree
  76.  *    sp:    page to split
  77.  *    key:    key to insert
  78.  *    data:    data to insert
  79.  *    flags:    BIGKEY/BIGDATA flags
  80.  *    ilen:    insert length
  81.  *    skip:    index to leave open
  82.  *
  83.  * Returns:
  84.  *    RET_ERROR, RET_SUCCESS
  85.  */
  86. int
  87. __bt_split(t, sp, key, data, flags, ilen, skip)
  88.     BTREE *t;
  89.     PAGE *sp;
  90.     const DBT *key, *data;
  91.     u_long flags;
  92.     size_t ilen;
  93.     u_int skip;
  94. {
  95.     BINTERNAL *bi;
  96.     BLEAF *bl, *tbl;
  97.     DBT a, b;
  98.     EPGNO *parent;
  99.     PAGE *h, *l, *r, *lchild, *rchild;
  100.     indx_t nxtindex;
  101.     size_t n, nbytes, nksize;
  102.     int parentsplit;
  103.     char *dest;
  104.  
  105.     /*
  106.      * Split the page into two pages, l and r.  The split routines return
  107.      * a pointer to the page into which the key should be inserted and with
  108.      * skip set to the offset which should be used.  Additionally, l and r
  109.      * are pinned.
  110.      */
  111.     h = sp->pgno == P_ROOT ?
  112.         bt_root(t, sp, &l, &r, &skip, ilen) :
  113.         bt_page(t, sp, &l, &r, &skip, ilen);
  114.     if (h == NULL)
  115.         return (RET_ERROR);
  116.  
  117.     /*
  118.      * Insert the new key/data pair into the leaf page.  (Key inserts
  119.      * always cause a leaf page to split first.)
  120.      */
  121.     h->linp[skip] = h->upper -= ilen;
  122.     dest = (char *)h + h->upper;
  123.     if (ISSET(t, R_RECNO))
  124.         WR_RLEAF(dest, data, flags)
  125.     else
  126.         WR_BLEAF(dest, key, data, flags)
  127.  
  128.     /* If the root page was split, make it look right. */
  129.     if (sp->pgno == P_ROOT &&
  130.         (ISSET(t, R_RECNO) ?
  131.         bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
  132.         goto err2;
  133.  
  134.     /*
  135.      * Now we walk the parent page stack -- a LIFO stack of the pages that
  136.      * were traversed when we searched for the page that split.  Each stack
  137.      * entry is a page number and a page index offset.  The offset is for
  138.      * the page traversed on the search.  We've just split a page, so we
  139.      * have to insert a new key into the parent page.
  140.      *
  141.      * If the insert into the parent page causes it to split, may have to
  142.      * continue splitting all the way up the tree.  We stop if the root
  143.      * splits or the page inserted into didn't have to split to hold the
  144.      * new key.  Some algorithms replace the key for the old page as well
  145.      * as the new page.  We don't, as there's no reason to believe that the
  146.      * first key on the old page is any better than the key we have, and,
  147.      * in the case of a key being placed at index 0 causing the split, the
  148.      * key is unavailable.
  149.      *
  150.      * There are a maximum of 5 pages pinned at any time.  We keep the left
  151.      * and right pages pinned while working on the parent.   The 5 are the
  152.      * two children, left parent and right parent (when the parent splits)
  153.      * and the root page or the overflow key page when calling bt_preserve.
  154.      * This code must make sure that all pins are released other than the
  155.      * root page or overflow page which is unlocked elsewhere.
  156.      */
  157.     while ((parent = BT_POP(t)) != NULL) {
  158.         lchild = l;
  159.         rchild = r;
  160.  
  161.         /* Get the parent page. */
  162.         if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
  163.             goto err2;
  164.  
  165.          /*
  166.          * The new key goes ONE AFTER the index, because the split
  167.          * was to the right.
  168.          */
  169.         skip = parent->index + 1;
  170.  
  171.         /*
  172.          * Calculate the space needed on the parent page.
  173.          *
  174.          * Prefix trees: space hack when inserting into BINTERNAL
  175.          * pages.  Retain only what's needed to distinguish between
  176.          * the new entry and the LAST entry on the page to its left.
  177.          * If the keys compare equal, retain the entire key.  Note,
  178.          * we don't touch overflow keys, and the entire key must be
  179.          * retained for the next-to-left most key on the leftmost
  180.          * page of each level, or the search will fail.  Applicable
  181.          * ONLY to internal pages that have leaf pages as children.
  182.          * Further reduction of the key between pairs of internal
  183.          * pages loses too much information.
  184.          */
  185.         switch (rchild->flags & P_TYPE) {
  186.         case P_BINTERNAL:
  187.             bi = GETBINTERNAL(rchild, 0);
  188.             nbytes = NBINTERNAL(bi->ksize);
  189.             break;
  190.         case P_BLEAF:
  191.             bl = GETBLEAF(rchild, 0);
  192.             nbytes = NBINTERNAL(bl->ksize);
  193.             if (t->bt_pfx && !(bl->flags & P_BIGKEY) &&
  194.                 (h->prevpg != P_INVALID || skip > 1)) {
  195.                 tbl = GETBLEAF(lchild, NEXTINDEX(lchild) - 1);
  196.                 a.size = tbl->ksize;
  197.                 a.data = tbl->bytes;
  198.                 b.size = bl->ksize;
  199.                 b.data = bl->bytes;
  200.                 nksize = t->bt_pfx(&a, &b);
  201.                 n = NBINTERNAL(nksize);
  202.                 if (n < nbytes) {
  203. #ifdef STATISTICS
  204.                     bt_pfxsaved += nbytes - n;
  205. #endif
  206.                     nbytes = n;
  207.                 } else
  208.                     nksize = 0;
  209.             } else
  210.                 nksize = 0;
  211.             break;
  212.         case P_RINTERNAL:
  213.         case P_RLEAF:
  214.             nbytes = NRINTERNAL;
  215.             break;
  216.         default:
  217.             abort();
  218.         }
  219.  
  220.         /* Split the parent page if necessary or shift the indices. */
  221.         if (h->upper - h->lower < nbytes + sizeof(indx_t)) {
  222.             sp = h;
  223.             h = h->pgno == P_ROOT ?
  224.                 bt_root(t, h, &l, &r, &skip, nbytes) :
  225.                 bt_page(t, h, &l, &r, &skip, nbytes);
  226.             if (h == NULL)
  227.                 goto err1;
  228.             parentsplit = 1;
  229.         } else {
  230.             if (skip < (nxtindex = NEXTINDEX(h)))
  231.                 memmove(h->linp + skip + 1, h->linp + skip,
  232.                     (nxtindex - skip) * sizeof(indx_t));
  233.             h->lower += sizeof(indx_t);
  234.             parentsplit = 0;
  235.         }
  236.  
  237.         /* Insert the key into the parent page. */
  238.         switch(rchild->flags & P_TYPE) {
  239.         case P_BINTERNAL:
  240.             h->linp[skip] = h->upper -= nbytes;
  241.             dest = (char *)h + h->linp[skip];
  242.             memmove(dest, bi, nbytes);
  243.             ((BINTERNAL *)dest)->pgno = rchild->pgno;
  244.             break;
  245.         case P_BLEAF:
  246.             h->linp[skip] = h->upper -= nbytes;
  247.             dest = (char *)h + h->linp[skip];
  248.             WR_BINTERNAL(dest, nksize ? nksize : bl->ksize,
  249.                 rchild->pgno, bl->flags & P_BIGKEY);
  250.             memmove(dest, bl->bytes, nksize ? nksize : bl->ksize);
  251.             if (bl->flags & P_BIGKEY &&
  252.                 bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
  253.                 goto err1;
  254.             break;
  255.         case P_RINTERNAL:
  256.             /*
  257.              * Update the left page count.  If split
  258.              * added at index 0, fix the correct page.
  259.              */
  260.             if (skip > 0)
  261.                 dest = (char *)h + h->linp[skip - 1];
  262.             else
  263.                 dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
  264.             ((RINTERNAL *)dest)->nrecs = rec_total(lchild);
  265.             ((RINTERNAL *)dest)->pgno = lchild->pgno;
  266.  
  267.             /* Update the right page count. */
  268.             h->linp[skip] = h->upper -= nbytes;
  269.             dest = (char *)h + h->linp[skip];
  270.             ((RINTERNAL *)dest)->nrecs = rec_total(rchild);
  271.             ((RINTERNAL *)dest)->pgno = rchild->pgno;
  272.             break;
  273.         case P_RLEAF:
  274.             /*
  275.              * Update the left page count.  If split
  276.              * added at index 0, fix the correct page.
  277.              */
  278.             if (skip > 0)
  279.                 dest = (char *)h + h->linp[skip - 1];
  280.             else
  281.                 dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
  282.             ((RINTERNAL *)dest)->nrecs = NEXTINDEX(lchild);
  283.             ((RINTERNAL *)dest)->pgno = lchild->pgno;
  284.  
  285.             /* Update the right page count. */
  286.             h->linp[skip] = h->upper -= nbytes;
  287.             dest = (char *)h + h->linp[skip];
  288.             ((RINTERNAL *)dest)->nrecs = NEXTINDEX(rchild);
  289.             ((RINTERNAL *)dest)->pgno = rchild->pgno;
  290.             break;
  291.         default:
  292.             abort();
  293.         }
  294.  
  295.         /* Unpin the held pages. */
  296.         if (!parentsplit) {
  297.             mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  298.             break;
  299.         }
  300.  
  301.         /* If the root page was split, make it look right. */
  302.         if (sp->pgno == P_ROOT &&
  303.             (ISSET(t, R_RECNO) ?
  304.             bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
  305.             goto err1;
  306.  
  307.         mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
  308.         mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
  309.     }
  310.  
  311.     /* Unpin the held pages. */
  312.     mpool_put(t->bt_mp, l, MPOOL_DIRTY);
  313.     mpool_put(t->bt_mp, r, MPOOL_DIRTY);
  314.  
  315.     /* Clear any pages left on the stack. */
  316.     return (RET_SUCCESS);
  317.  
  318.     /*
  319.      * If something fails in the above loop we were already walking back
  320.      * up the tree and the tree is now inconsistent.  Nothing much we can
  321.      * do about it but release any memory we're holding.
  322.      */
  323. err1:    mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
  324.     mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
  325.  
  326. err2:    mpool_put(t->bt_mp, l, 0);
  327.     mpool_put(t->bt_mp, r, 0);
  328.     __dbpanic(t->bt_dbp);
  329.     return (RET_ERROR);
  330. }
  331.  
  332. /*
  333.  * BT_PAGE -- Split a non-root page of a btree.
  334.  *
  335.  * Parameters:
  336.  *    t:    tree
  337.  *    h:    root page
  338.  *    lp:    pointer to left page pointer
  339.  *    rp:    pointer to right page pointer
  340.  *    skip:    pointer to index to leave open
  341.  *    ilen:    insert length
  342.  *
  343.  * Returns:
  344.  *    Pointer to page in which to insert or NULL on error.
  345.  */
  346. static PAGE *
  347. bt_page(t, h, lp, rp, skip, ilen)
  348.     BTREE *t;
  349.     PAGE *h, **lp, **rp;
  350.     u_int *skip;
  351.     size_t ilen;
  352. {
  353.     PAGE *l, *r, *tp;
  354.     pgno_t npg;
  355.  
  356. #ifdef STATISTICS
  357.     ++bt_split;
  358. #endif
  359.     /* Put the new right page for the split into place. */
  360.     if ((r = __bt_new(t, &npg)) == NULL)
  361.         return (NULL);
  362.     r->pgno = npg;
  363.     r->lower = BTDATAOFF;
  364.     r->upper = t->bt_psize;
  365.     r->nextpg = h->nextpg;
  366.     r->prevpg = h->pgno;
  367.     r->flags = h->flags & P_TYPE;
  368.  
  369.     /*
  370.      * If we're splitting the last page on a level because we're appending
  371.      * a key to it (skip is NEXTINDEX()), it's likely that the data is
  372.      * sorted.  Adding an empty page on the side of the level is less work
  373.      * and can push the fill factor much higher than normal.  If we're
  374.      * wrong it's no big deal, we'll just do the split the right way next
  375.      * time.  It may look like it's equally easy to do a similar hack for
  376.      * reverse sorted data, that is, split the tree left, but it's not.
  377.      * Don't even try.
  378.      */
  379.     if (h->nextpg == P_INVALID && *skip == NEXTINDEX(h)) {
  380. #ifdef STATISTICS
  381.         ++bt_sortsplit;
  382. #endif
  383.         h->nextpg = r->pgno;
  384.         r->lower = BTDATAOFF + sizeof(indx_t);
  385.         *skip = 0;
  386.         *lp = h;
  387.         *rp = r;
  388.         return (r);
  389.     }
  390.  
  391.     /* Put the new left page for the split into place. */
  392.     if ((l = malloc(t->bt_psize)) == NULL) {
  393.         mpool_put(t->bt_mp, r, 0);
  394.         return (NULL);
  395.     }
  396.     l->pgno = h->pgno;
  397.     l->nextpg = r->pgno;
  398.     l->prevpg = h->prevpg;
  399.     l->lower = BTDATAOFF;
  400.     l->upper = t->bt_psize;
  401.     l->flags = h->flags & P_TYPE;
  402.  
  403.     /* Fix up the previous pointer of the page after the split page. */
  404.     if (h->nextpg != P_INVALID) {
  405.         if ((tp = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) {
  406.             free(l);
  407.             /* XXX mpool_free(t->bt_mp, r->pgno); */
  408.             return (NULL);
  409.         }
  410.         tp->prevpg = r->pgno;
  411.         mpool_put(t->bt_mp, tp, 0);
  412.     }
  413.  
  414.     /*
  415.      * Split right.  The key/data pairs aren't sorted in the btree page so
  416.      * it's simpler to copy the data from the split page onto two new pages
  417.      * instead of copying half the data to the right page and compacting
  418.      * the left page in place.  Since the left page can't change, we have
  419.      * to swap the original and the allocated left page after the split.
  420.      */
  421.     tp = bt_psplit(t, h, l, r, skip, ilen);
  422.  
  423.     /* Move the new left page onto the old left page. */
  424.     memmove(h, l, t->bt_psize);
  425.     if (tp == l)
  426.         tp = h;
  427.     free(l);
  428.  
  429.     *lp = h;
  430.     *rp = r;
  431.     return (tp);
  432. }
  433.  
  434. /*
  435.  * BT_ROOT -- Split the root page of a btree.
  436.  *
  437.  * Parameters:
  438.  *    t:    tree
  439.  *    h:    root page
  440.  *    lp:    pointer to left page pointer
  441.  *    rp:    pointer to right page pointer
  442.  *    skip:    pointer to index to leave open
  443.  *    ilen:    insert length
  444.  *
  445.  * Returns:
  446.  *    Pointer to page in which to insert or NULL on error.
  447.  */
  448. static PAGE *
  449. bt_root(t, h, lp, rp, skip, ilen)
  450.     BTREE *t;
  451.     PAGE *h, **lp, **rp;
  452.     u_int *skip;
  453.     size_t ilen;
  454. {
  455.     PAGE *l, *r, *tp;
  456.     pgno_t lnpg, rnpg;
  457.  
  458. #ifdef STATISTICS
  459.     ++bt_split;
  460.     ++bt_rootsplit;
  461. #endif
  462.     /* Put the new left and right pages for the split into place. */
  463.     if ((l = __bt_new(t, &lnpg)) == NULL ||
  464.         (r = __bt_new(t, &rnpg)) == NULL)
  465.         return (NULL);
  466.     l->pgno = lnpg;
  467.     r->pgno = rnpg;
  468.     l->nextpg = r->pgno;
  469.     r->prevpg = l->pgno;
  470.     l->prevpg = r->nextpg = P_INVALID;
  471.     l->lower = r->lower = BTDATAOFF;
  472.     l->upper = r->upper = t->bt_psize;
  473.     l->flags = r->flags = h->flags & P_TYPE;
  474.  
  475.     /* Split the root page. */
  476.     tp = bt_psplit(t, h, l, r, skip, ilen);
  477.  
  478.     *lp = l;
  479.     *rp = r;
  480.     return (tp);
  481. }
  482.  
  483. /*
  484.  * BT_RROOT -- Fix up the recno root page after it has been split.
  485.  *
  486.  * Parameters:
  487.  *    t:    tree
  488.  *    h:    root page
  489.  *    l:    left page
  490.  *    r:    right page
  491.  *
  492.  * Returns:
  493.  *    RET_ERROR, RET_SUCCESS
  494.  */
  495. static int
  496. bt_rroot(t, h, l, r)
  497.     BTREE *t;
  498.     PAGE *h, *l, *r;
  499. {
  500.     char *dest;
  501.  
  502.     /* Insert the left and right keys, set the header information. */
  503.     h->linp[0] = h->upper = t->bt_psize - NRINTERNAL;
  504.     dest = (char *)h + h->upper;
  505.     WR_RINTERNAL(dest,
  506.         l->flags & P_RLEAF ? NEXTINDEX(l) : rec_total(l), l->pgno);
  507.  
  508.     h->linp[1] = h->upper -= NRINTERNAL;
  509.     dest = (char *)h + h->upper;
  510.     WR_RINTERNAL(dest,
  511.         r->flags & P_RLEAF ? NEXTINDEX(r) : rec_total(r), r->pgno);
  512.  
  513.     h->lower = BTDATAOFF + 2 * sizeof(indx_t);
  514.  
  515.     /* Unpin the root page, set to recno internal page. */
  516.     h->flags &= ~P_TYPE;
  517.     h->flags |= P_RINTERNAL;
  518.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  519.  
  520.     return (RET_SUCCESS);
  521. }
  522.  
  523. /*
  524.  * BT_BROOT -- Fix up the btree root page after it has been split.
  525.  *
  526.  * Parameters:
  527.  *    t:    tree
  528.  *    h:    root page
  529.  *    l:    left page
  530.  *    r:    right page
  531.  *
  532.  * Returns:
  533.  *    RET_ERROR, RET_SUCCESS
  534.  */
  535. static int
  536. bt_broot(t, h, l, r)
  537.     BTREE *t;
  538.     PAGE *h, *l, *r;
  539. {
  540.     BINTERNAL *bi;
  541.     BLEAF *bl;
  542.     size_t nbytes;
  543.     char *dest;
  544.  
  545.     /*
  546.      * If the root page was a leaf page, change it into an internal page.
  547.      * We copy the key we split on (but not the key's data, in the case of
  548.      * a leaf page) to the new root page.
  549.      *
  550.      * The btree comparison code guarantees that the left-most key on any
  551.      * level of the tree is never used, so it doesn't need to be filled in.
  552.      */
  553.     nbytes = NBINTERNAL(0);
  554.     h->linp[0] = h->upper = t->bt_psize - nbytes;
  555.     dest = (char *)h + h->upper;
  556.     WR_BINTERNAL(dest, 0, l->pgno, 0);
  557.  
  558.     switch(h->flags & P_TYPE) {
  559.     case P_BLEAF:
  560.         bl = GETBLEAF(r, 0);
  561.         nbytes = NBINTERNAL(bl->ksize);
  562.         h->linp[1] = h->upper -= nbytes;
  563.         dest = (char *)h + h->upper;
  564.         WR_BINTERNAL(dest, bl->ksize, r->pgno, 0);
  565.         memmove(dest, bl->bytes, bl->ksize);
  566.  
  567.         /*
  568.          * If the key is on an overflow page, mark the overflow chain
  569.          * so it isn't deleted when the leaf copy of the key is deleted.
  570.          */
  571.         if (bl->flags & P_BIGKEY &&
  572.             bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
  573.             return (RET_ERROR);
  574.         break;
  575.     case P_BINTERNAL:
  576.         bi = GETBINTERNAL(r, 0);
  577.         nbytes = NBINTERNAL(bi->ksize);
  578.         h->linp[1] = h->upper -= nbytes;
  579.         dest = (char *)h + h->upper;
  580.         memmove(dest, bi, nbytes);
  581.         ((BINTERNAL *)dest)->pgno = r->pgno;
  582.         break;
  583.     default:
  584.         abort();
  585.     }
  586.  
  587.     /* There are two keys on the page. */
  588.     h->lower = BTDATAOFF + 2 * sizeof(indx_t);
  589.  
  590.     /* Unpin the root page, set to btree internal page. */
  591.     h->flags &= ~P_TYPE;
  592.     h->flags |= P_BINTERNAL;
  593.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  594.  
  595.     return (RET_SUCCESS);
  596. }
  597.  
  598. /*
  599.  * BT_PSPLIT -- Do the real work of splitting the page.
  600.  *
  601.  * Parameters:
  602.  *    t:    tree
  603.  *    h:    page to be split
  604.  *    l:    page to put lower half of data
  605.  *    r:    page to put upper half of data
  606.  *    pskip:    pointer to index to leave open
  607.  *    ilen:    insert length
  608.  *
  609.  * Returns:
  610.  *    Pointer to page in which to insert.
  611.  */
  612. static PAGE *
  613. bt_psplit(t, h, l, r, pskip, ilen)
  614.     BTREE *t;
  615.     PAGE *h, *l, *r;
  616.     u_int *pskip;
  617.     size_t ilen;
  618. {
  619.     BINTERNAL *bi;
  620.     BLEAF *bl;
  621.     RLEAF *rl;
  622.     EPGNO *c;
  623.     PAGE *rval;
  624.     void *src;
  625.     indx_t full, half, nxt, off, skip, top, used;
  626.     size_t nbytes;
  627.     int bigkeycnt, isbigkey;
  628.  
  629.     /*
  630.      * Split the data to the left and right pages.  Leave the skip index
  631.      * open.  Additionally, make some effort not to split on an overflow
  632.      * key.  This makes internal page processing faster and can save
  633.      * space as overflow keys used by internal pages are never deleted.
  634.      */
  635.     bigkeycnt = 0;
  636.     skip = *pskip;
  637.     full = t->bt_psize - BTDATAOFF;
  638.     half = full / 2;
  639.     used = 0;
  640.     for (nxt = off = 0, top = NEXTINDEX(h); nxt < top; ++off) {
  641.         if (skip == off) {
  642.             nbytes = ilen;
  643.             isbigkey = 0;        /* XXX: not really known. */
  644.         } else
  645.             switch (h->flags & P_TYPE) {
  646.             case P_BINTERNAL:
  647.                 src = bi = GETBINTERNAL(h, nxt);
  648.                 nbytes = NBINTERNAL(bi->ksize);
  649.                 isbigkey = bi->flags & P_BIGKEY;
  650.                 break;
  651.             case P_BLEAF:
  652.                 src = bl = GETBLEAF(h, nxt);
  653.                 nbytes = NBLEAF(bl);
  654.                 isbigkey = bl->flags & P_BIGKEY;
  655.                 break;
  656.             case P_RINTERNAL:
  657.                 src = GETRINTERNAL(h, nxt);
  658.                 nbytes = NRINTERNAL;
  659.                 isbigkey = 0;
  660.                 break;
  661.             case P_RLEAF:
  662.                 src = rl = GETRLEAF(h, nxt);
  663.                 nbytes = NRLEAF(rl);
  664.                 isbigkey = 0;
  665.                 break;
  666.             default:
  667.                 abort();
  668.             }
  669.  
  670.         /*
  671.          * If the key/data pairs are substantial fractions of the max
  672.          * possible size for the page, it's possible to get situations
  673.          * where we decide to try and copy too much onto the left page.
  674.          * Make sure that doesn't happen.
  675.          */
  676.         if (skip <= off && used + nbytes >= full) {
  677.             --off;
  678.             break;
  679.         }
  680.  
  681.         /* Copy the key/data pair, if not the skipped index. */
  682.         if (skip != off) {
  683.             ++nxt;
  684.  
  685.             l->linp[off] = l->upper -= nbytes;
  686.             memmove((char *)l + l->upper, src, nbytes);
  687.         }
  688.  
  689.         used += nbytes;
  690.         if (used >= half) {
  691.             if (!isbigkey || bigkeycnt == 3)
  692.                 break;
  693.             else
  694.                 ++bigkeycnt;
  695.         }
  696.     }
  697.  
  698.     /*
  699.      * Off is the last offset that's valid for the left page.
  700.      * Nxt is the first offset to be placed on the right page.
  701.      */
  702.     l->lower += (off + 1) * sizeof(indx_t);
  703.  
  704.     /*
  705.      * If splitting the page that the cursor was on, the cursor has to be
  706.      * adjusted to point to the same record as before the split.  If the
  707.      * cursor is at or past the skipped slot, the cursor is incremented by
  708.      * one.  If the cursor is on the right page, it is decremented by the
  709.      * number of records split to the left page.
  710.      *
  711.      * Don't bother checking for the B_SEQINIT flag, the page number will
  712.      * be P_INVALID.
  713.      */
  714.     c = &t->bt_bcursor;
  715.     if (c->pgno == h->pgno) {
  716.         if (c->index >= skip)
  717.             ++c->index;
  718.         if (c->index < nxt)            /* Left page. */
  719.             c->pgno = l->pgno;
  720.         else {                    /* Right page. */
  721.             c->pgno = r->pgno;
  722.             c->index -= nxt;
  723.         }
  724.     }
  725.  
  726.     /*
  727.      * If the skipped index was on the left page, just return that page.
  728.      * Otherwise, adjust the skip index to reflect the new position on
  729.      * the right page.
  730.      */
  731.     if (skip <= off) {
  732.         skip = 0;
  733.         rval = l;
  734.     } else {
  735.         rval = r;
  736.         *pskip -= nxt;
  737.     }
  738.  
  739.     for (off = 0; nxt < top; ++off) {
  740.         if (skip == nxt) {
  741.             ++off;
  742.             skip = 0;
  743.         }
  744.         switch (h->flags & P_TYPE) {
  745.         case P_BINTERNAL:
  746.             src = bi = GETBINTERNAL(h, nxt);
  747.             nbytes = NBINTERNAL(bi->ksize);
  748.             break;
  749.         case P_BLEAF:
  750.             src = bl = GETBLEAF(h, nxt);
  751.             nbytes = NBLEAF(bl);
  752.             break;
  753.         case P_RINTERNAL:
  754.             src = GETRINTERNAL(h, nxt);
  755.             nbytes = NRINTERNAL;
  756.             break;
  757.         case P_RLEAF:
  758.             src = rl = GETRLEAF(h, nxt);
  759.             nbytes = NRLEAF(rl);
  760.             break;
  761.         default:
  762.             abort();
  763.         }
  764.         ++nxt;
  765.         r->linp[off] = r->upper -= nbytes;
  766.         memmove((char *)r + r->upper, src, nbytes);
  767.     }
  768.     r->lower += off * sizeof(indx_t);
  769.  
  770.     /* If the key is being appended to the page, adjust the index. */
  771.     if (skip == top)
  772.         r->lower += sizeof(indx_t);
  773.  
  774.     return (rval);
  775. }
  776.  
  777. /*
  778.  * BT_PRESERVE -- Mark a chain of pages as used by an internal node.
  779.  *
  780.  * Chains of indirect blocks pointed to by leaf nodes get reclaimed when the
  781.  * record that references them gets deleted.  Chains pointed to by internal
  782.  * pages never get deleted.  This routine marks a chain as pointed to by an
  783.  * internal page.
  784.  *
  785.  * Parameters:
  786.  *    t:    tree
  787.  *    pg:    page number of first page in the chain.
  788.  *
  789.  * Returns:
  790.  *    RET_SUCCESS, RET_ERROR.
  791.  */
  792. static int
  793. bt_preserve(t, pg)
  794.     BTREE *t;
  795.     pgno_t pg;
  796. {
  797.     PAGE *h;
  798.  
  799.     if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  800.         return (RET_ERROR);
  801.     h->flags |= P_PRESERVE;
  802.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  803.     return (RET_SUCCESS);
  804. }
  805.  
  806. /*
  807.  * REC_TOTAL -- Return the number of recno entries below a page.
  808.  *
  809.  * Parameters:
  810.  *    h:    page
  811.  *
  812.  * Returns:
  813.  *    The number of recno entries below a page.
  814.  *
  815.  * XXX
  816.  * These values could be set by the bt_psplit routine.  The problem is that the
  817.  * entry has to be popped off of the stack etc. or the values have to be passed
  818.  * all the way back to bt_split/bt_rroot and it's not very clean.
  819.  */
  820. static recno_t
  821. rec_total(h)
  822.     PAGE *h;
  823. {
  824.     recno_t recs;
  825.     indx_t nxt, top;
  826.  
  827.     for (recs = 0, nxt = 0, top = NEXTINDEX(h); nxt < top; ++nxt)
  828.         recs += GETRINTERNAL(h, nxt)->nrecs;
  829.     return (recs);
  830. }
  831.